#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
void Swap(int* p1, int* p2)
{
	int tmp = *p1;
	*p1 = *p2;
	*p2 = tmp;
}
void Print(int* p, int n)
{
	for (int i = 0; i < n; i++) {
		printf("%d ", p[i]);
	}
	printf("\n");
}
void QuickSort(int* p,int begin,int end)
{
	if (begin >= end) {
		return;
	}
	int lefti = begin, righti = end;
	int keyi = begin;
	while (lefti < righti) {
		while (lefti < righti && p[righti] >= p[keyi]) {
			righti--;
		}
		while (lefti < righti && p[lefti] <= p[keyi]) {
			lefti++;
		}
		Swap(&p[lefti], &p[righti]);
	}

	Swap(&p[keyi], &p[lefti]);
	QuickSort(p, begin, lefti - 1);
	QuickSort(p, lefti+1, end);
}
void test()
{
	int arr[] = { 5,4,3,6,1,2,9,9,5,6,0,3 };
	int size = sizeof(arr) / sizeof(int);
	QuickSort(arr,0,size-1);
	Print(arr, size);

}
int main()
{
	test();

	return 0;
}